1. Field of Invention
The invention relates generally to methods and apparatus implementing a monitor wait operation in an object-based computing system. More particularly, the invention relates to methods and apparatus for a thread to atomically release a monitor lock and enter a corresponding wait queue in an object-based computing system.
2. Description of Relevant Art
Within an object-based environment, threads are often used to satisfy requests for services. A thread may be thought of as a xe2x80x9csketch padxe2x80x9d of storage resources, and is essentially a single sequential flow of control within a computer program. In general, a thread, or a xe2x80x9cthread of control,xe2x80x9d is a sequence of central processing unit (CPU) instructions or programming language statements that may be independently executed. Each thread has its own execution stack on which method activations reside. As will be appreciated by those skilled in the art, when a method is activated with respect to a thread, an activation is xe2x80x9cpushedxe2x80x9d on the execution stack of the thread. When the method returns, or is deactivated, the activation is xe2x80x9cpoppedxe2x80x9d from the execution stack.
Since an activation of one method may activate another method, an execution stack operates in a first-in-last-out manner.
During the execution of an object-based program, a thread may attempt to execute operations that involve multiple objects. On the other hand, multiple threads may attempt to execute operations that involve a single object. Frequently, only one thread is allowed to invoke one of some number of operations, i.e., synchronized operations, that involve a particular object at any given time. That is, only one thread may be allowed to execute a synchronized operation on a particular object at one time. A synchronized operation, e.g., a synchronized method, is block-structured in that it requires that the thread invoking the method to first synchronize with the object that the method is invoked on, and desynchronize with that object when the method returns. Synchronizing a thread with an object generally entails controlling access to the object using a synchronization construct before invoking the method.
Synchronization constructs such as locks, mutexes, semaphores, and monitors may be used to control access to shared resources during periods in which allowing a thread to operate on shared resources would be inappropriate. By way of example, in order to prevent more than one thread from operating on an object at any particular time, objects are often provided with locks. The locks are arranged such that only the thread that has possession of the lock for an object is permitted to execute a method on that object. With respect to FIG. 1, a process of acquiring an object lock will be described. The process of acquiring an object lock begins at step 104 where a thread obtains the object on which the thread wishes to operate. In general, the object on which the thread intends to operate has an associated object lock. Then, in step 106, a determination is made regarding whether the object is locked. That is, a determination is made regarding whether the object lock associated with the object is held by another thread, e.g., a thread that is currently operating on the object.
If the determination in step 106 is that the object is not locked, then the thread acquires the object lock in step 108. Alternatively, if the object is locked, then the thread waits for the object to be unlocked in step 110. Once the object is unlocked, process flow moves from step 110 to step 108 where the object is locked by the thread.
As previously mentioned, a thread is permitted to execute a synchronized operation on an object if it successfully acquires the lock on the object. While one thread holds the lock on an object, other threads may be allowed to attempt to execute additional synchronization operations on the object, and may execute non-synchronized operations on the object. Thread synchronization is a process by which threads may interact to check the status of objects, whether the objects are locked or unlocked, while allowing only the thread which holds an object lock to execute synchronized operations on the locked object. Thread synchronization also enables threads to obtain and remove object locks.
When threads are synchronized, in order to make certain that only the thread that possesses an object lock is allowed to operate on a locked object, synchronization constructs are generally provided. One such synchronization construct is known in the art as the monitor. Monitors are simple yet fundamental thread synchronization constructs used in, for example, the JAVA(trademark) platform of the Sun Microsystems Corporation of Palo Alto, Calif. Typically, monitors are implemented using low-level synchronization primitives such as mutexes and the like.
In some situations, a thread owning a target object""s monitor may wish to release the target object""s monitor and suspend execution by issuing what is referred to as a wait operation. When a thread calls a monitor wait operation, all synchronization locks on the target object associated with the thread are released allowing other threads to enter the monitor (i.e.; get the mutex) associated with the target object. After release of the synchronization locks, the thread is placed (enqueued) in the wait queue associated with the target object until such time as (1) another thread calls a notify method or a notifyALL method, or (2) a timeout period has elapsed. As known in the art, the notify method removes an arbitrary thread from the wait queue which then competes for the mutex on the target object, whereas a notifyALL method removes all threads from the wait queue.
The conventional method of implementing a monitor wait operation presents a number of problems. One such problem occurs when a notification is lost. For example, if a first thread is attempting to issue a monitor wait it must first release the monitor lock and prepare to sleep (i.e.; suspend execution). If, however, a second thread grabs the target object""s lock and issues a monitor notify before the first thread has entered the wait queue, the notification will be lost since wait queue is empty. In this case, the first thread will be sleeping until the timeout period has elapsed wasting valuable time in the process.
Another problem associated with the conventional approach to issuing a monitor wait is related to inappropriate queuing order in the wait queue. Inappropriate queuing order may arise if during the period of time between a first thread releasing a monitor lock and entering an associated wait queue, a second thread enters the monitor and issues its own monitor wait. In this case, the second thread may enter the wait queue before the first thread thereby compromising the queuing order.
And still another problem associated with the conventional approach to issuing a monitor wait is related to those situations where a notifyALL is issued by the monitor owner. In this case, all waiting threads then compete for the object lock which causes a substantial waste of CPU time. It should also be noted that in some cases, a timeout, a thread interrupt, and a wait notification may occur substantially simultaneously which cannot be supported by most monitor implementations. Therefore, an improved method and apparatus for implementing a monitor wait operation is desirable.
Broadly speaking, the invention relates to an improved method, apparatus and computer system for implementing an atomic monitor wait operation. According to one aspect of the invention, a computer-implemented method for implementing an atomic monitor wait operation includes creating a semaphore specific to a first thread desiring to exit a monitor associated with a target object. The semaphore is then placed in a wait queue (enqueued) associated with the target object. After the enqueuing, the first thread releases the lock on the target object allowing a second thread to execute a synchronous operation on the target object.
According to still another aspect of the invention, computer program product for implementing an atomic monitor wait operation is disclosed. The computer program product includes computer code that creates a semaphore specific to a first thread desiring to exit a monitor associated with a target object having an object lock as well as computer code that places the semaphore in a wait queue associated with the target object. The computer program product includes computer code that releases the object lock by the first thread thereby allowing a second thread to execute a synchronous operation on the target object, and a computer readable medium that stores the computer codes.
According to yet another aspect of the present invention, a computer system includes a memory and a plurality of threads. The computer system also includes a processor coupled to the memory an object including an object monitor and an associated wait queue, the object monitor being arranged to include information relating to the ownership of object, a first thread selected from the plurality of threads that has locked the object; and a semaphore created by and specific to the first thread. In a preferred embodiment, the first thread places the semaphore into the wait queue 5 prior to releasing an object lock in furtherance of an atomic monitor wait operation.